cdef long calc_q(long n, long i=0, long cols=0, long diags=0, long trans=0):
    cdef long j;
    cdef long col;
    cdef long diag;
    cdef long tran;
    cdef long rt;
    if i == n:
        return 1
    else:
        rt = 0
        for j in range(n):
            col = 1 << j
            diag = 1 << (i - j + n - 1)
            tran = 1 << (i + j)
            if (col & cols) == 0 and (diag & diags) == 0 and (tran & trans) == 0:
                rt += calc_q(n, i + 1, cols | col, diags | diag, trans | tran)
        return rt


def calc( n,  i=0,  cols=0,  diags=0,  trans=0):
    return  calc_q(n,i,cols,diags,trans)